Conservation of Information and Coevolution: New BIO-Complexity Article by Ewert and Marks

In a previous article I described Winston Ewert, Robert Marks, and William Dembski’s book Introduction to Evolutionary Informatics which identifies the limitations of evolutionary algorithms to find solutions for complex problems. The book demonstrates that this class of programs is only capable of achieving non-trivial results unless information about desired outcomes is programmed into them. For instance, a program designed to find the best strategy for playing checkers must have detailed information about the game programmed into its search method. It could not develop a strategy to play chess without altering the underlying algorithm to include new chess-related information.

This constraint is a direct result of No Free Lunch (NFL) theorems and the related law of Conservation of Information. Attempts have been make to overcome this challenge by appealing to what are termed coevolutionary searches. However, as Ewert and Marks demonstrate in a new article for the journal BIO-Complexity, these algorithms do not escape the NFL barrier, so they are no more efficient on average than random searches.

Evolutionary algorithms typically follow a standard set of steps. They generate trial solutions to a problem, and then assign each trial some “fitness” value. These values are then used to determine how the next iteration of trials is generated for testing. The process continues until a target is found.

Ewert and Marks use the illustration of generating recipes for making pancakes. In this example, a trial recipe represents a list of the specific amounts of each ingredient and details of the cooking, such as burner setting and times. The assigned value corresponds to the prepared pancake’s taste, and it determines how new recipes are generated. The process continues until a pancake is created that meets some taste standard. The set of values associated with all possible trials is described as a fitness landscape, and the search algorithm must navigate its terrain looking for targets. For standard algorithms, all information needed to assign a fitness value is known. In contrast, for coevolutionary algorithms information is not fully known, so incomplete or “subjacent” information must often be used. That’s because the fitness landscape continuously changes due to the presence of other organisms or other contingent factors.

This difference can be illustrated in terms of an examples from biological evolution. A standard evolutionary algorithm would correspond to an organism having a specific “fitness” which remains fairly constant in most situations. For instance, that of a desert plant might relate to such innate abilities as conserving water and processing sunlight. A computer program could model the plant’s fitness using related variables, such as the plant’s mass and the amount of chlorophyll produced in its leaves. These variables would fully determine the assigned fitness value. In contrast, a coevolutonary process would correspond to the fitness changing over time due to such factors as interactions with other species and details of the physical environment. For instance, chemicals in the skin could provide greater or lesser protection from different predators, and the shape of the plant could prove more or less helpful in different settings.

To model this increased complexity, the algorithms generate a query matrix where a row is assigned to each candidate solution, and each column corresponds to a different factor affecting fitness such as interactions with a particular species. Many cells in this matrix are often not known, whether due to computational or other practical limitations, so various methods are employed to assign each trial solution (row) an aggregate value based on the limited knowledge. The algorithm then proceeds as with traditional models. Many have claimed that coevolutionary programs can find solutions to a wide variety of problems more quickly on average than random searches, thus overcoming the restrictions of the NFL theorems. In other words, they eliminate the need for programmers to provide problem-specific “active information” to guide searches.

To test this claim, Ewert and Marks measured the performance of various coevolutionary algorithms for a variety of problems. They found that they could at best match the performance of traditional “full-search” methods, and they typically performed worse. Their article also describes how claims to the contrary were based on research that focused on solving very simple problems or that designed experiments in such a way as to provide hidden information to assist in finding targets. Therefore, coevolutionary processes cannot overcome NFL limitations, as they also require problem-specific information to perform properly.

These results have direct implications for Darwinian evolution. Biologists often claim that coevolutionary interactions between different species or species and the environment can alter the underlying fitness landscape in such a way as to drive evolutionary changes. A classic example is the proposed coevolution of bees and flowering plants. Many plants need insects as carriers for their pollen. As a result, the presence of insects places selective pressure on the plants to produce smells, colors, and nectar to attract them. In turn, the presence of the plants places selective pressures on the insects to move toward the plants’ signals to obtain the food supply. In addition, insects are selected for thicker hairs on their legs to capture more pollen. They can then fertilize more plants resulting in a greater food supply. Such scenarios may sound plausible, but they only result in trivial adjustments to preexisting structures.

In contrast, complex innovations, such as new body plans, require radical innovations which, in turn, require large amounts of new information. The environment is often claimed to provide this new information, which is believed to be hidden in the fitness landscapes coupled to coevolutionary interactions. However, this research by Ewert and Marks directly challenges the claim. The search space corresponding to biological forms is vastly greater than what could be searched through random mutations in the offspring of any species. And natural selection cannot help without being provided large amounts of information on where new forms reside. For coevolutionary processes are no more efficient at solving problems than traditional evolutionary algorithms, and the latter are no more efficient on average than random searches.